#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include <mem.h>
#include <time.h>

#include "function_test.h"

int aiDataForSort[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70, 71, 65, 78, 129,29, 29, 29  };
int idatalen = 0;


/**
 * 打印其中的数据
 * @return
 */
int print_data(){
    int ifor = 0;
    for( ifor=0; ifor<idatalen; ifor++ ){
        printf( "  %d,  ", aiDataForSort[ifor]);
    }
    printf("\n");
}

/**
 * 交换两个数值
 * @param a
 * @param b
 */
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

/**
 *  buble sort
 *  冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，
 *  如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。
 */
int buble_sort( int aiInput[], int ilen ){
    int i = 0;
    int j = 0;
    int itemp = 0;
    for(  i=0; i<ilen-1; i++){
        for (j = 0;  j< ilen-i-1; j++) {
            if( aiInput[j] < aiInput[j+1] ){
                itemp = aiInput[j];
                aiInput[j] = aiInput[j+1];
                aiInput[j+1] = itemp;
            }
        }
    }
    return 0;
}

/**
 * select sort
 * 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，
 * 存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 * 以此类推，直到所有元素均排序完毕。
 * @return
 */
 int select_sort( int aiInput[], int ilen ){
     int iMinIndex = 0;
     for( int i=0; i<ilen; i++){
         iMinIndex = i;
         for (int j = i+1; j <ilen ; j++) {
            if( aiInput[j]<aiInput[iMinIndex]){
                iMinIndex = j;
            }
         }
         swap( &aiInput[i],  &aiInput[iMinIndex] );
     }
     return 0;
 }

 /**
  * 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
  * 类似扑克牌排序
  * @param aiInput
  * @param ilen
  */
 void  insert_sort( int aiInput[], int ilen ){
     for( int i=0; i<ilen; i++){
         for( int j=i; j>0 &&  aiInput[j]<aiInput[j-1]   ;j--){
             swap( &aiInput[j],  &aiInput[j-1] );
         }
     }
 }

 /**
  * 折半插入排序思想：基本功能与普通插入排序类似，只是查找部分使用折半查找法查找
  *
  */
void  half_find_insert_sort( int aiInput[], int ilen ){
    for( int i=1; i<ilen; i++){
        int ilowIndex = 0;
        int iheightIndex = i-1;
        int imidIndex = 0;
        int iTemp = aiInput[i];
        /**
         * 此处找到 ilowIndex位置，这个位置上的值 >=iTemp 需要比较的这个值
         */
        while( ilowIndex<=iheightIndex){
            imidIndex = ( ilowIndex+iheightIndex)/2;
            if( aiInput[imidIndex] <iTemp ){
                ilowIndex = imidIndex + 1;
            }else{
                iheightIndex = imidIndex-1;
            }
        }// while
        /**
         *  chong i-1处向  ilowIndex处， 平移数据
         */
        for( int j=i-1;  j>=ilowIndex; j--){
            aiInput[j+1] = aiInput[j];
        }
        /**
         *ilowIndex处的数据赋值
         */
        aiInput[ilowIndex] = iTemp;
    }// for( int i=0; i<ilen; i++){
}

/**
 * 希尔排序是插入排序的改进版， O n （3/2）
 *
 * 希尔增量： ht = N / 2, h[k] = h[k+1] / 2，即 {N/2, (N / 2)/2, ..., 1}
 * Hibbard增量： {1, 3, ..., 2^k-1}
 */
void shell_sort( int aiInput[], int ilen ){
    int iMaxStep = 0;
    int iTemp = ilen-1;
    int iStep = 0;
    while(iTemp>0 ){
        iMaxStep++;
        iTemp = iTemp>>1;
    }
    printf( " iMaxStep = %d \n", iMaxStep  );
    while( iMaxStep>=1){
        iStep = pow( 2, iMaxStep) -1;
        for( int i=iMaxStep; i<ilen; i++){
            for( int j=i; j>0; j=j-iMaxStep){
                if( aiInput[j] < aiInput[j-iMaxStep]){
                    swap( &aiInput[j],  &aiInput[j-iMaxStep] );
                }
            }// for j
        }// for i

        iMaxStep--;
    }
}

/**
 *  归并排序
 *  归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。
 *  从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，
 *      再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果。
 *  从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：
 *      分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
 *      求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
 *      合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。
 *      实际上从上往下的排序方法是一种递归方式实现的；
 */

/**
 * 合并两个有序的数组
 */
void merge(int a[], int start, int mid, int end)
{
    int *tmp = (int *)malloc((end-start+1)*sizeof(int));    // tmp是汇总2个有序区的临时区域
    int i = start;            // 第1个有序区的索引
    int j = mid + 1;        // 第2个有序区的索引
    int k = 0;                // 临时区域的索引

    while(i <= mid && j <= end)
    {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }

    /**
     * 经过上面的循环， a[ i], a[j]中肯定有一个已经为空了，就是说下面两个循环，肯定只有一个循环能够运行
     */
    while(i <= mid)
        tmp[k++] = a[i++];

    while(j <= end)
        tmp[k++] = a[j++];

    // 将排序后的元素，全部都整合到数组a中。
    printf( " \n tmp k=%d\n   ", k);
    for (i = 0; i < k; i++){
        printf( "  %d   ", tmp[i]);
    }
    printf( " \n a  start=%d  \n   ", start);

    for (i = 0; i < k; i++){
        printf( "  %d   ", a[start + i]);
    }
    printf( "  \n   ");

    /*
    for (i = 0; i < k; i++){
        a[start + i] = tmp[i];
    }
    //*/

    memmove( a+start, tmp, k*sizeof(int));
    printf( "  after move \n   ");
    for (i = 0; i < k; i++){
        printf( "  %d   ", a[start + i]);
    }
    printf( "  \n   ");

    free(tmp);
    tmp = NULL;
}

/**
 * 合并两个有序的数组， self
 * @param aiInput
 */
void  merge_two_simple( int aiInput[], int iFirstStart, int iFirstLen, int iSecondStart, int  iSecondlen){
      int iDataLen = iFirstLen + iSecondlen;
      int iSortIndex = 0;
      int iFirstIndex = iFirstStart;
      int iSecondIndex = iSecondStart;
      int *piData = (int *)malloc( iDataLen*sizeof(int));
      if( NULL == piData  || iDataLen<=0){
          printf( " merge_two_simple malloc error  \n"  );
          return;
      }
      while( iSortIndex<iDataLen ){
          if( iSecondIndex<iSecondStart+iSecondlen &&  iFirstIndex<iFirstStart+iFirstLen ){
              if(  aiInput[iFirstIndex] > aiInput[iSecondIndex]){
                  piData[iSortIndex] = aiInput[iSecondIndex];
                  iSecondIndex++;
              }else{
                  piData[iSortIndex] = aiInput[iFirstIndex];
                  iFirstIndex++;
              }
              iSortIndex++;
          }else if( iSecondIndex<iSecondStart+iSecondlen &&  iFirstIndex>=iFirstStart+iFirstLen ){
              //
              piData[iSortIndex] = aiInput[iSecondIndex];
              iSecondIndex++;
              iSortIndex++;
          }else if(  iSecondIndex>=iSecondStart+iSecondlen &&  iFirstIndex<iFirstStart+iFirstLen){
              piData[iSortIndex] = aiInput[iFirstIndex];
              iFirstIndex++;
              iSortIndex++;
          }
      }
      memcpy(  aiInput + iFirstStart, piData, iDataLen*sizeof(int) );
      if( NULL != piData){
          free( piData);
          piData = NULL;
      }
}

/**
 * 递归方式实现归并排序
 */
void  merge_sort_uptodown( int aiInput[], int istart ,int iend ){

    if(  NULL==aiInput || istart>=iend){
        return;
    }
    int  iMidIndex = (istart + iend )/2;
    merge_sort_uptodown( aiInput, istart,  iMidIndex );
    merge_sort_uptodown( aiInput, iMidIndex+1, iend);
    merge_two_simple( aiInput, istart, iMidIndex-istart+1, iMidIndex+1,  iend-iMidIndex  );
    //merge(aiInput, istart, iMidIndex,  iend);

}


/**
 * 自下而上实现归并排序，就是分组，分组排序， 合并排序
 * @return
 */
void  merge_sort_downtoup( int aiInput[], int ilen ){
    if( NULL == aiInput || ilen<=0){
        return;
    }
    int iStep = 0;
    for( int i=1; i<ilen; i=i*2){
        //merge_downtoup( aiInput, ilen,  i);
        int itwoLen = i*2;
        int j = 0;
        int iMidIndex = 0;
        for(  j=0; j+itwoLen-1<ilen; j=j+itwoLen){
            iMidIndex = j+i-1;
            merge( aiInput, j,  iMidIndex, j+itwoLen-1);
        }
        /**
         * 查看是否有落单的分组, 这里是循环判断重要的部分
         * 这块有这样写的 if( j+i-1<ilen-1) 实际上经过上面的循环；
         * 剩下的数据肯定是落单的数据,并且 j +i-1肯定小于ilen
         */
        if( j<ilen){
            iMidIndex = j+i-1;
            merge( aiInput, j,  iMidIndex, ilen-1);
        }
    }

}

/**
 * 快速排序(Quick Sort)使用分治法策略。
 * 它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数
 * 据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 * 快速排序流程：
 * (1) 从数列中挑出一个基准值。
 * (2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，
 * 该基准就处于数列的中间位置。
 * (3) 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。
 *
 * 随机快速排序中使用 ，使用 index 的随机值，避免对已排序队列排序时出现问题
 * 取得[0,x)的随机整数：rand()%x；
 * 取得[0,x]的随机整数：rand()%(x+1)；
 * 取得[a,b)的随机整数：rand()%(b-a)+a；
 * 取得(a,b]的随机整数：rand()%(b-a)+a+1；
 * 取得[a,b]的随机整数：rand()%(b-a+1)+a；
 * 取得0-1之间的浮点数：rand()/double(RAND_MAX)。
 *
 */
 void quick_sort( int aiInput[], int leftIndex, int rightIndex ){
    /**
     * 这里要优先判断 leftIndex<rightIndex
     */
     int  i = leftIndex;
     int  j = rightIndex;
     if( i>=j){
         return;
     }
    /*
    * 易错写为aiInput[0]
    */

    int  iRandIndex = rand()%(rightIndex-leftIndex+1) + leftIndex;
    printf("rand leftIndex = %d , iRandIndex=%d\n", leftIndex,  iRandIndex);
    int  iBaseValue = aiInput[iRandIndex];
    aiInput[iRandIndex] = aiInput[leftIndex];
    aiInput[leftIndex] = iBaseValue;

     while( i<j){
        /**
         *  从最右边找第一个小于 iBaseValue 的值，将该值赋值给 aiInput[i]
         */
         while ( aiInput[j]>iBaseValue && j>i){
             j--;
         }
         /**
          * 这里存在 减去1后，i == j的情况
          */
         if( i<j ){
             aiInput[i] = aiInput[j];
             i++;
         }
         /**
          * 从左到右搜索第一个大于iBaseValue的值，将该值赋值给 aiInput[j]
          */
          while(aiInput[i]<iBaseValue && j>i ){
              i++;
          }
          if( i<j){
              aiInput[j] = aiInput[i];
              j--;
          }
     }
     /**
      * 此时 i == j
      */
     aiInput[i] = iBaseValue;
    quick_sort( aiInput, leftIndex, i-1 );
    quick_sort( aiInput,  i+1, rightIndex);
 }


 /**
  * 计数排序（桶排序）， 只限对整数进行排序
  *   1、花 O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max
  *   2、开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)
  *   3、数组 B 中 index 的元素记录的值是 A 中某元素出现的次数
  *   4、最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数
  * @return
  */

 void  count_sort( int aiInput[], int ilen ){
     int iMaxValue = aiInput[0];
     int iMinValue = aiInput[0];
     int iBarrLen = 0;
     int *pBarrry = NULL;
     int i = 0;
     int iIndexTemp = 0;
     /**
      * 获取最大最小值
      */
     for( i=0; i< ilen; i++){
         if( aiInput[i] > iMaxValue){
             iMaxValue = aiInput[i];
         }
         if( aiInput[i] <iMinValue){
             iMinValue = aiInput[i];
         }
     }

     /**
      * 构建新数组 B
      */
     iBarrLen = iMaxValue - iMinValue + 1;
     pBarrry = (int *)malloc( sizeof(int) *  iBarrLen);
     if( NULL == pBarrry){
         return;
     }
     memset( pBarrry, 0, iBarrLen*sizeof(int));

     /**
      * 统计各个数的出现次数
      */
      for( i=0; i<ilen; i++){
          iIndexTemp = aiInput[i] - iMinValue;
          pBarrry[iIndexTemp] = pBarrry[iIndexTemp] + 1;
      }

     /**
      * 根据数组B 构建排序后数据
      */
     iIndexTemp = 0;
     for( i=0; i<iBarrLen; i++){
         while( pBarrry[i] > 0 ){
             aiInput[iIndexTemp] = iMinValue + i;
             pBarrry[i] =  pBarrry[i] - 1;
             iIndexTemp++;
         }
     }

     if(pBarrry){
         free(pBarrry);
         pBarrry = NULL;
     }
 }

/**
 *   基数排序
 *   基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
 *   具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。
 *   这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
 */
void  Radix_sort( int aiInput[], int ilen ){
    /**
     * 获取最大值
     */
    int iMaxValue = aiInput[0];
    int i = 0;
    int j = 0;
    int iMaxDecimalPlaces = 1;
    int iDivisor  = 1;
    int iarrPos[10] = { 0};
    int itempIndexInArrPos = 0;
    int *piarrOutput = NULL;
    piarrOutput = ( int *)malloc( sizeof( int ) * ilen);
    if( !piarrOutput){
        return;
    }

    for( i=0; i< ilen; i++){
        if( aiInput[i] > iMaxValue){
            iMaxValue = aiInput[i];
        }
    }

    /**
     *  根据最大值获取最大位数，这里有一个快速获取数字位数的方法，就是建立对比类别，如 9， 99， 999， 9999，这样对比就可以
     *  一般不会超过10位，此处使用 /10方式实现；
     */
     i = iMaxValue;
    while( i/10>0){
        iMaxDecimalPlaces++;
        i = i/10;
    }

    /**
     * 根据 iMaxDecimalPlaces 值进行几次排序
     */
    for( i=0; i<iMaxDecimalPlaces; i++){
        /**
         * 这里要注意，每次新的循环，需要重新统计对应位数的个数，所以需要清空
         */
        memset( iarrPos, 0, sizeof(int)*10);
        /**
         * 统计对应位置上数据的个数
         */
        for( j=0; j<ilen; j++){
            iarrPos[ aiInput[j]/iDivisor%10]++;
        }

        /**
         * 将对应位置上的个数，转变为piarrOutput对应的位置
         */
         for( j=1; j<10; j++){
             iarrPos[j] += iarrPos[j - 1];
         }

         /**
          * 将数据根据本次分类，写入piarrOutput
          */
        for( j=ilen-1; j>=0; j--){
            itempIndexInArrPos = iarrPos[ aiInput[j]/iDivisor%10 ];
            /**
             * 这里因为 itempIndexInArrPos 这个值是统计过的，所以不会存在这个数为0的情况
             * 由于数组从0开始，统计iarrPos[j]时是个数，类似长度，转换为数组下标就得-1
             * piarrOutput 赋值完成后，需要从iarrPos中减去 1，个数减少了，对应位置也向前移
             * 此处这样写主要是 使用 一维数组解决二维数组问题
             *
             */
            piarrOutput[itempIndexInArrPos-1] = aiInput[j];
            iarrPos[aiInput[j]/iDivisor%10 ]--;
        }

        /**
         * 将此处排序后的数据copy到 aiInput，用于下次排序
         */
        memmove(  aiInput, piarrOutput, sizeof(int)*ilen);
        iDivisor = iDivisor*10;
    }//for( i=1; i<iMaxDecimalPlaces; i++){


    if( piarrOutput){
        free(piarrOutput);
        piarrOutput = NULL;
    }

}


int main() {
    printf("Hello, World!\n");
    int iret = 0;

    idatalen = sizeof(aiDataForSort )/ sizeof(int);
    printf( "data len = %d\n",idatalen);

    //buble_sort( aiDataForSort, idatalen);
    //select_sort( aiDataForSort, idatalen);
    //insert_sort( aiDataForSort, idatalen);
    //half_find_insert_sort( aiDataForSort, idatalen);
    //shell_sort( aiDataForSort, idatalen);
    //merge_sort_uptodown( aiDataForSort, 0, idatalen-1);
    //merge_sort_downtoup( aiDataForSort, idatalen);
    //quick_sort( aiDataForSort, 0, idatalen-1);
    //count_sort( aiDataForSort, idatalen);
    //Radix_sort( aiDataForSort, idatalen);
    print_data();

    //DP_print_test();
    //DP_corn_sum_test();
    iret = getGcdNumber_Euclid( 16, 4);
    printf( "getGcdNumber_Euclid iret = %d\n",iret);
    iret = getGcdNumber_Stein( 609404, 6);
    printf( "getGcdNumber_Stein iret = %d\n",iret);

    iret = getMinNumberThroughBrigeTest();
    printf( "getMinNumberThroughBrigeTest iret = %d\n",iret);


    return 0;
}